#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
// 求数组长度
#define ARR_LEN(arr) (sizeof(arr) / sizeof(arr[0]))
// 交换数组中的两个元素
#define SWAP(arr, i, j ) {			\
	int tmp = arr[i];			\
	arr[i] = arr[j];			\
	arr[j] = tmp;			\
}
// 打印数组的函数
void print_arr(int arr[], int left, int right) {
	for (int i = left; i <= right; i++) {
		printf("%d ", arr[i]);
	}
	printf("\n");
}

// 分区是快速排序的核心逻辑
static int partition(int arr[], int left, int right) {
	// 1.随机挑选一个元素作为基准值，交换到数组末尾
	int pivot_idx = left + rand() % (right - left + 1);
	int pivot = arr[pivot_idx];
	SWAP(arr, pivot_idx, right);

	// 2.初始化两个索引，一个索引find_idx用于遍历数组用于寻找比基准值小的元素
	// 另一个索引min_idx用于标记下一个比基准值小的元素放置的位置
	// 这两个索引都从left开始，向右遍历
	int min_idx = left;
	for (int find_idx = left; find_idx < right; find_idx++) {
		if (arr[find_idx] < pivot) {
			SWAP(arr, find_idx, min_idx);
			min_idx++;
		}
	}
	// 3.当上面循环结束时，find_idx遍历到末尾的基准值，min_idx此时指向的是第一个比基准值大的元素
	// 于是交换这两个元素，此时基准值就排序好了，返回基准值的下标
	SWAP(arr, right, min_idx);

	// 完成了一次分区操作，打印一下基准值和数组内容
	printf("pivot = %d  ", pivot);
	print_arr(arr, left, right);
	return min_idx;
}

static void partition_recursion(int arr[], int left, int right) {
	// 递归的出口
	if (left >= right) {
		return;
	}
	// 递归体
	int idx = partition(arr, left, right);
	partition_recursion(arr, left, idx - 1);
	partition_recursion(arr, idx + 1, right);
}


// 该函数就是对外提供接口，就是提供单向分区快排的功能
void quick_sort_one_way(int arr[], int len) {
	srand(time(NULL));
	partition_recursion(arr, 0, len - 1);
}
int main(void) {
	// 测试单向分区快速排序
	int arr[] = { 8,3,2,6,9,5,10,20,30,1,3,5 };
	int len = ARR_LEN(arr);
	print_arr(arr, 0, len - 1);
	quick_sort_one_way(arr, len);
	return 0;
}